package leetcode.code0321;

import leetcode.helper.HelpDebug;

public class Solution_Stack extends Solution321 {

	public int[] maxNumber(int[] nums1, int[] nums2, int k) {
		int[] ans = new int[k];
		for (int i = 0; i <= k; i++) {
			if (i <= nums1.length && k - i <= nums2.length) {
				int[] a1 = f(nums1, i);
				int[] a2 = f(nums2, k - i);
				int[] a = merge(a1, a2);
				if (ge(a, ans)) {
					ans = a;
				}
			}
		}
		return ans;
	}

	private int[] f(int[] nums, int k) {
		if (k == 0)
			return null;
		int[] ans = new int[k];
		for (int i = 0, p = 0; i < nums.length; i++) {
			int cur = nums[i];
			while (p > 0 && cur > ans[p - 1] && nums.length - i + p - 1 >= k) {
				p--;
			}
			if (p < k)
				ans[p++] = cur;
		}
		return ans;
	}

	private boolean ge(int[] a, int[] ans) {
		if (a == null)
			return false;
		for (int i = 0; i < ans.length; i++) {
			if (a[i] == ans[i]) {
				continue;
			}
			if (a[i] > ans[i]) {
				return true;
			} else {
				return false;
			}
		}
		return false;
	}

	private int[] merge(int[] a1, int[] a2) {
		if (a1 == null)
			return a2;
		if (a2 == null)
			return a1;
		int[] ans = new int[a1.length + a2.length];
		int p1 = 0, p2 = 0, p = 0;
		while (p1 < a1.length && p2 < a2.length) {
			if (a1[p1] < a2[p2]) {
				ans[p++] = a2[p2++];
			} else if (a1[p1] > a2[p2]) {
				ans[p++] = a1[p1++];
			} else {
				// 相等
				if (ff(a1, p1, a2, p2) > 0) {
					ans[p++] = a1[p1++];
				} else {
					ans[p++] = a2[p2++];
				}
			}
		}
		while (p1 < a1.length) {
			ans[p++] = a1[p1++];
		}
		while (p2 < a2.length) {
			ans[p++] = a2[p2++];
		}
		return ans;
	}

	private int ff(int[] a1, int p1, int[] a2, int p2) {
		while (p1 < a1.length && p2 < a2.length) {
			if (a1[p1] == a2[p2]) {
				p1++;
				p2++;
			} else {
				return a1[p1] - a2[p2];
			}
		}
		return p1 < a1.length ? 1 : -1;
	}

	public static void main(String[] args) {
		Solution_Stack so = new Solution_Stack();
		int[] nums1 = HelpDebug.str2array3("[3,4,6,5]");
		int[] nums2 = HelpDebug.str2array3("[9,1,2,5,8,3]");
		int k = 5;
		int[] e = HelpDebug.str2array3("[9,8,6,5,3]");
		int[] r = so.maxNumber(nums1, nums2, k);
		HelpDebug.compare(e, r);

//		[2,5,6,4,4,0]
//		[7,3,8,0,6,5,7,6,2]
//		15

//		[7,3,8,2,5,6,4,4,0,0,6,5,7,6,2]
//		[7,3,8,2,5,6,4,4,0,6,5,7,6,2,0]
		Integer s = Integer.valueOf("2000");
//		s.substring(8, 10);
		System.out.println(s.equals(2000));
		
	}

}
